public class LeetCode50 {
    public double myPow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        return fastPow(x, N);
    }
    private double fastPow(double x, long n) {
        if (n == 0) {
            return 1.0;
        }
        // 计算一半的结果
        double half = fastPow(x, n / 2);

        // 如果 n 是偶数，则直接返回 half 的平方
        // 如果 n 是奇数，则需要额外乘以 x
        if (n % 2 == 1) {
            return half * half * x;
        } else {
            return half * half;
        }
    }
}
